//given two jugs with capacity B and S, B > S, measure P where 0 <= P <= B
#include <iostream>
#include <algorithm>
#include <memory>
#include <queue>
#include <stack>
#include <vector>
#include <utility>

struct Jug{
	Jug(int c, int v = 0) : capacity(c), value(v) {};
	void empty(){value = 0;}
	void fill(){value = capacity;}
	Jug& pour_to(Jug& rhs);

	const int capacity;
	int value;
};
Jug& Jug::pour_to(Jug& rhs){
	int y = rhs.capacity - rhs.value;
	int pour = std::min(value,y);
	value -= pour;
	rhs.value += pour;
	return *this;
}

struct State{
	State(int B, int bvalue, int S, int svalue) :Big(B, bvalue), Small(S, svalue), visited(false) {}
	Jug Big;
	Jug Small;
	bool visited;
	std::shared_ptr<State> predecessor;
};

bool is_goal(const State& s, int P){
	return s.Big.value == P || s.Small.value == P;
}

struct Node{
	Node(int BC, int SC,int BV = 0, int SV = 0) : B(BC), S(SC), b(BV), s(SV) {}
	std::pair<int,int> fill_b() { return std::make_pair(B, s); }
	std::pair<int,int> fill_s() { return std::make_pair(b, S); }
	std::pair<int,int> empty_b() { return std::make_pair(0, s); }
	std::pair<int,int> empty_s() { return std::make_pair(b, 0); }
	std::pair<int,int> pour_bs();
	std::pair<int,int> pour_sb();
	const int B, S;
	int b, s;
};
std::pair<int,int> Node::pour_bs() {
	int s_remain = S-s;
	int v = std::min(b, s_remain);
	return std::make_pair(b-v, s+v);
}

std::pair<int,int> Node::pour_sb() {
	int b_remain = B-b;
	int v = std::min(s, b_remain);
	return std::make_pair(b+v, s-v);
}

void process(std::vector<std::vector<std::pair<int,int> > > predecessor, int i, int j){
	std::stack<std::pair<int,int> > stack;
	std::pair<int,int> init(-1,-1);
	std::pair<int,int> goal(i,j);
	while(i >= 0 && j >= 0){
		stack.push(std::make_pair(i,j));
		std::pair<int,int> pre = predecessor[i][j];
		i = pre.first;
		j = pre.second;
	}
	while(!stack.empty()){
		std::pair<int,int> next = stack.top();
		stack.pop();
		std::cout << "(" << next.first << "," << next.second << ")";
		if(!stack.empty())
			std::cout << " -> ";
	}
	std::cout << std::endl;
}

bool bfs(int B, int S, int P){
	std::vector<std::vector<bool> > visited(B+1, std::vector<bool>(S+1,false));
	std::vector<std::vector<std::pair<int,int> > > predecessor(B+1, std::vector<std::pair<int,int> >(S+1, std::make_pair(-1,-1)));
	std::queue<std::pair<int,int> > queue;
	visited[0][0] = true;
	queue.push(std::make_pair(0,0));
	while(!queue.empty()){
		std::pair<int,int> curr = queue.front();
		queue.pop();
		Node curr_node(B, S, curr.first, curr.second);
		std::queue<std::pair<int,int> > candidates;
		//OP 1
		std::pair<int,int> next = curr_node.empty_b();
		candidates.push(next);
		//OP 2
		next = curr_node.empty_s();
		candidates.push(next);
		//OP 3
		next = curr_node.fill_b();
		candidates.push(next);
		//OP 4
		next = curr_node.fill_s();
		candidates.push(next);
		//OP 5
		next = curr_node.pour_bs();
		candidates.push(next);
		//OP 6
		next = curr_node.pour_sb();
		candidates.push(next);
		while(!candidates.empty()){
			next = candidates.front();
			candidates.pop();
			if(!visited[next.first][next.second]){
				visited[next.first][next.second] = true;
				predecessor[next.first][next.second] = std::make_pair(curr.first,curr.second);
				queue.push(std::make_pair(next.first, next.second));
				if(next.first == P || next.second == P) {
					process(predecessor,next.first,next.second);
					return true;
				}
			}
		}
	}
	return false;
}

bool dfs(int B, int S, int P){
	std::vector<std::vector<bool> > visited(B+1, std::vector<bool>(S+1,false));
	std::vector<std::vector<std::pair<int,int> > > predecessor(B+1, std::vector<std::pair<int,int> >(S+1, std::make_pair(-1,-1)));
	std::stack<std::pair<int,int> > stack;
	visited[0][0] = true;
	stack.push(std::make_pair(0,0));
	while(!stack.empty()){
		std::pair<int,int> curr = stack.top();
		stack.pop();
		Node curr_node(B, S, curr.first, curr.second);
		std::queue<std::pair<int,int> > candidates;
		//OP 1
		std::pair<int,int> next = curr_node.empty_b();
		candidates.push(next);
		//OP 2
		next = curr_node.empty_s();
		candidates.push(next);
		//OP 3
		next = curr_node.fill_b();
		candidates.push(next);
		//OP 4
		next = curr_node.fill_s();
		candidates.push(next);
		//OP 5
		next = curr_node.pour_bs();
		candidates.push(next);
		//OP 6
		next = curr_node.pour_sb();
		candidates.push(next);
		while(!candidates.empty()){
			next = candidates.front();
			candidates.pop();
			if(!visited[next.first][next.second]){
				visited[next.first][next.second] = true;
				predecessor[next.first][next.second] = std::make_pair(curr.first,curr.second);
				stack.push(std::make_pair(next.first, next.second));
				if(next.first == P || next.second == P) {
					process(predecessor,next.first,next.second);
					return true;
				}
			}
		}
	}
	return false;
}

void test_two_jugs(){
	std::cout << "breath first search:\n";
	bfs(5,17,8);
	std::cout << "depth first search:\n";
	dfs(5,17,8);
}